//
// Description: 57. 插入区间
// Created by Loading on 2025/4/15.
//

#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> insert(vector<vector<int>> &intervals, vector<int> &newInterval) {
    vector<vector<int>> res;

    int start = newInterval[0], end = newInterval[1];
    bool insert = false; // 是否已插入新区间
    for (const auto &v : intervals) {
        if (v[1] < start) { // 左侧无交集
            res.emplace_back(v);
        } else if (v[0] > end) { // 右侧无交集
            if (!insert) {
                res.push_back({start, end});
                insert = true;
            }
            res.emplace_back(v);
        } else { // 存在交集，更新左右端点
            start = min(start, v[0]);
            end = max(end, v[1]);
        }
    }

    if (!insert) { // 遍历完成依然没有插入新区间，表示新区间左端点最大，追加至最后
        res.push_back({start, end});
    }

    return res;
}

int main() {
    vector<vector<int>> intervals{{1, 2}};
    vector<int> newInterval{4, 8};

    auto res = insert(intervals, newInterval);

    for (const auto &v : res) {
        cout << v[0] << ',' << v[1] << endl;
    }

    return 0;
}
